Count Univalue Subtrees

Given a binary tree, count the number of uni-value subtrees.

A Uni-value subtree means all nodes of the subtree have the same value.

For example:

Given binary tree,

  1.               5
  2.              / \
  3.             1   5
  4.            / \   \
  5.           5   5   5

return 4.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   int count;
  13.   public int countUnivalSubtrees(TreeNode root) {
  14.     count = 0;
  15.     helper(root);
  16.     return count;
  17.   }
  19.   boolean helper(TreeNode root) {
  20.     if (root == null)
  21.       return true;
  23.     boolean left = helper(root.left);
  24.     boolean right = helper(root.right);
  26.     if (left && right && (root.left == null || root.val == root.left.val) && (root.right == null || root.val == root.right.val)) {
  27.       count++;
  28.       return true;
  29.     }
  31.     return false;
  32.   }
  33. }

Check Univalue Tree

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public boolean isUnivalTree(TreeNode root) {
  12.     if (root == null)
  13.       return false;
  15.     return helper(root, root.val);
  16.   }
  18.   boolean helper(TreeNode root, in val) {
  19.     if (root == null)
  20.       return true;
  22.     if (root.val != val)
  23.       return false;
  25.     return helper(root.left, val) && helper(root.right, val);
  26.   }
  27. }